package org.tang.tianchi.notes.array;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * 示例 1：
 * <p>
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 示例 2：
 * <p>
 * 输入：nums = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：nums = [0]
 * 输出：[]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 3000
 * -105 <= nums[i] <= 105
 */
public class 三数之和 {
    private static int value = 0;

    private static void setValue(){
        value = 7;
        System.out.println(value);
    }

    public static void main(String[] args) {
        setValue();
        System.out.println(value);
//        int[] nums = getArray(-184,790,10);
//        int[] nums = new int[]{1,2,-2,-1};
//        System.out.println(Arrays.toString(nums));
//        int target = 3;
//        System.out.println(threeSum02(nums));
    }

    /**
     * 暴力求解：
     * 要实现不重复，必须a <= b <= c  -》Arrays.sort(nums);
     * 每一次的数据不能重复枚举，比如[-1,0,0,1,1]，第一次满足的数据[-1，0，1], 下标为first = 0,second = 1, third =3; 第二次满足的数据也是[-1，0，1],下标为first = 0,second = 2, third =3;
     * 设置第一个下标为first,第二个下标为second,第三个下标为third
     * 那么在枚举以上三个数的时候，均不允许枚举到同一个数字-》条件一
     * 完成条件一，比如first枚举到了0，在nums中，下一次枚举也是0，需要跳到1；因为是逐渐增大的，那么只需要当前的枚举不等于上一次枚举，那么可视为不重复
     * 即：nums[first] != nums[first - 1]
     * 当是第一个数的时候，是允许选择的，因为它没有前一个数，所以可以枚举；  所以下标选择有条件时，注意最开始和最末尾。
     * first完整的表达式：if first != 0 && nums[first] != nums[first - 1]  ；同理 second和third
     * 求：满足条件：nums[first] + nums[second] + nums[third] == 0，由于不能重复，在first和second确定的情况，third选择第一个满足条件的，然后进行second的第二个循环
     * 即：if (nums[first] + nums[second] + nums[third] == 0) {check()}
     * 伪代码
     * Arrays.sort(nums)
     * // for first = 0...n-2
     * //     只有和上一次元素不同，才进行枚举
     * //     if first == 0 or nums[first] != nums[first - 1] then
     * //        for second = first + 1...n-1
     * //            if second == first + 1 or nums[second] != nums[second - 1] then
     * //                for third = second + 1...n
     * //                    check(first, second, third)
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> value = new ArrayList<>();
        if (nums.length < 3) {
            return value;
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                for (int m = j + 1; m < nums.length; m++) {
                    if (nums[i] + nums[j] + nums[m] == 0) {
                        List<Integer> list = new ArrayList<>(3);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[m]);
                        value.add(list);
                        break;
                    }
                }
            }
        }
        return value;
    }


    /**
     * 在1的情况下，可以优化
     * 在和值一定的情况下，first确定，second在上升，third在下降
     * 循环倒排，保留和值刚好不大于0的third值，
     * if first + second + third == 0 then add()
     * second++,third还是刚刚的临界值，check()直到和值不大于0
     * 同时，third不能小于等于second
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum02(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> value = new ArrayList<>();
        if (nums.length < 3) {
            return value;
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int third = nums.length - 1;
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                while (nums[i] + nums[j] + nums[third] > 0 && third > j) {
                    third--;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (j == third) {
                    break;
                }
                if (nums[i] + nums[j] + nums[third] == 0) {
                    List<Integer> list = new ArrayList<>(3);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[third]);
                    value.add(list);
                }
            }
        }
        return value;
    }
}
